Genetic programming and genetic algorithms provide a computional optimisation strategy for problems which are difficult to solve using conventional mathematical techniques. They are particularly applied to highly complex situations, where a very large number of variable parameters prevents any formal attempt at a solution. A typical example of such a problem is where a lorry has to make deliveries to many different sites at various locations, and it is desired to select the shortest route which visits all the necessary sites (this is sometimes referred to as the "travelling salesman" problem, and arises for example in the placement of components and links in a printed circuit board). When the number of sites to be visited is very large, it is not feasible to determine a solution by an exhaustive calculation of the distance for every possible route.
Instead, one way of addressing the problem is to use a genetic algorithm. According to this approach, a set of different possible routes are selected, each being typically represented in practical implementations by a fixed length string, and the distance for each selected route is calculated (this is known as the "fitness"). Then, a new set of routes is generated by forming essentially random combinations of routes from the preceding set, with those routes having the shortest distances (ie best fitness) being preferentially selected for the reproduction of routes into the next generation. The fitness of each member of the new generation is then calculated, and the process is repeated, for example until a predetermined number of generations is reached, or until an individual having a particular fitness level has been produced. Some industrial applications of genetic algorithms are described in "Genetic based Machine Learning--Applications in Industry and Commerce" by Terence C Fogarty, Neil S Ireson, and Lawrence Bull, in the Proceedings of the Conference on Adaptive Computing and Information Processing, in the UK, Jan 25-27, 1994, vol 2, page 509-530,
Thus the genetic algorithm mimics natural evolution, in that for each generation, the least successful members are destroyed, and only the most successful members produce progeny for the next generation. In time, it is hoped that the quality of the population steadily improves, eventually leading to an optimal solution. In simplest terms, each cycle of the genetic algorithm involves an evaluation phase for the current population, and then a generation phase, for producing the next population.
Genetic programming is similar to a genetic algorithm, but differs in that in the former, it is essentially the program itself which is changed between generations, rather than some input string, as for the latter. A comprehensive description of genetic programming can be found in "Genetic programming: on the programming of computers by means of natural selection" by John Koza, MIT Press, 1992 (ISBN 0-262-11170-5), and at the WorldWideWeb site: "Genetic Programming FAQ" at (http://www.salford.ac.uk/docs/depts/eee/gp2faq.html).
One of the main disadvantages of genetic algorithms and genetic programming is that they can be very computer-intensive, often requiring extensive computing power. Many people have therefore explored the possibility of using a parallel approach to genetic algorithms. This is particularly appropriate given the inherently parallel nature of many of the operations involved in genetic algorithms (for example in many variations the evaluation phase involves an independent calculation of merit for each member of the population).
Examples of prior art work on distributed or parallel genetic algorithms are: "Multilevel Distributed Genetic Algorithms", by P Osmera, I Simonik, and J Roupec, in Proceedings of the 1st International Conference on Genetic Algorithms in Engineering Systems, 1995, p505-510; "Optimization in a Distributed Processing Environment using Genetic Algorithms with Multivariate Crossover" by A Konstam, S Hartley, and W Carr, Proceedings of CSC 92, ACM 20th Annual Computer Science Conference, Mar. 3-5 1992, p109-116; "A Distributed Parallel Genetic Algorithm for Solving Optimal Growth Models" by P Beaumont and P Bradshaw, in Computational Economics, Vol 8, No 3, August 1995, p159-179; "Minimum Weight Design of Large Structures on a Network of Workstations" by Skumar and H Adeli, in Microcomputers in Civil Engineering, Vol 10, Number 6, November 1995, page 423-432; "A Genetic Approach to Dynamic Load Balancing in a Distributed Computing System" by M Munetomo, Y Takai, and Y Sato, in Proceedings of the 1st IEEE Conference on Evolutionary Computation, Jun. 27-29, 1994, vol 1, p418-421; and "A Summary of Research on Parallel Genetic Algorithms" by E Cantu-Paz, IlliGAL Report No 95007, July 1995, from the Genetic Algorithms Laboratory at the University of Illinois, USA.
Recently, there have been a couple of attempts to use the Internet in genetic programming. For example, "Genetic Programming of Music", by Jeffrey Putnam, New Mexico Institue of Mining and Technology (accessible from http://www.nmt.edu/.about.jefu/notes/notes.html) describes the use of genetic programming to produce a short segment of music. This method involved posting members of the current population to the WorldWideWeb (WWW) on the Internet, where a large number of people who were visting the site could listen to the segments, and rank them. This would then allow the next population of musical segments to be generated from the most popular members of the current set. Note that in this method, where the evaluation comprised a subjective, human judgement, the Internet simply provided a highly effective means of making the test musical segments available to a large number of listeners/evaluators. Apparently a somewhat similar approach has been taken in an attempt to generate aesthetically pleasing images.
There is also interest in using the Internet for running a simulation of evolution, as described in "A Life in Silicon", by Joe Flower, in the New Scientist, Jun. 15, 1996, p33-36. Essentially, a large number of computer programs have been released onto the Internet, in a project which seeks to mimic the effects of natural selection. The Internet is used because it provides a cheap, and very diverse, environment. Each node incorporated into the environment appears to run a host operating program (referred to as Tierra). Note that this project is simply an attempt to build a computer model of evolution. It does not aim to solve some external problem, and so does not represent genetic programming per se.
Despite the above work, the use of parallel or distributed genetic programming has still proved somewhat too slow for many commercial applications, and so has met with only limited success outside the scientific research community.